package com.practice.sequence;

/**
 * You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
 * algorithm to find the maximum sub sequence which has equal number of 1s and
 * 0s.
 */
public class LongestEqual01 {
	public int longest(String a) {
		int N = a.length();
		int[] b = new int[N+1];
		
		b[0] = 0;
		for (int i=1; i<=N; i++) {
			b[i] = b[i-1] + (a.charAt(i-1)=='0'? 1 : -1);
		}
		if (b[N] > 0) for (int i=0; i<=N; i++) b[i] = -b[i];
		
		int k = -b[N];
		int[] left = new int[k+1];
		
		int t = 0;
		for (int i=0; i<=N && t<=k; i++) {
			if (b[i] == -t) {
				left[t] = i;
				t++;
			}
		}
		
		int max = 0;
		t = -k;
		for (int i=N; i>=0 && t<=0; i--) {
			if (b[i] == t) {
				max = Math.max(max, i - left[-t]);
				t++;
			}
		}
		
		return max;
	}
}
